#include <stdio.h>
#include <stdlib.h>

// 定义链表节点结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

// 创建一个新节点
ListNode* createNode(int val) {
    ListNode *newNode = (ListNode*)malloc(sizeof(ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 合并两个排序链表
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 创建一个虚拟头节点
    ListNode dummy;
    ListNode *tail = &dummy;
    dummy.next = NULL;

    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // 连接剩余的节点
    if (l1 != NULL) {
        tail->next = l1;
    } else {
        tail->next = l2;
    }

    return dummy.next;
}

// 打印链表
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->val);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 测试代码
int main() {
    // 创建第一个排序链表 1 -> 3 -> 5
    ListNode* l1 = createNode(1);
    l1->next = createNode(3);
    l1->next->next = createNode(5);

    // 创建第二个排序链表 2 -> 4 -> 6
    ListNode* l2 = createNode(2);
    l2->next = createNode(4);
    l2->next->next = createNode(6);

    // 合并链表
    ListNode* mergedList = mergeTwoLists(l1, l2);

    // 打印合并后的链表
    printList(mergedList);

    // 释放内存 (省略实现)

    return 0;
}
